package 动态规划.dp声明正序And倒序.射箭比赛这道题的思维发散;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/25 22:36
 */
public class leetcode368最大整除子集 {

    /*
     从这个题可以去学习一下 dp 倒推:
     然后,再去 练习 射箭比赛!
     ==
     强化 回溯的 能力!
     */


    /*
     有时间 可以再折腾一下 , 这个 回溯到底能不能 实现,虽然时间复杂度肯定是会挂掉的
     因为这里的 n 比较大!
     */

    private List<Integer> ans;
    private int max;

    public List<Integer> solution(int nums[]) {
//        if(nums.length == 1){
//            return Arrays.asList(nums[0]);
//        }
        Arrays.sort(nums);
        recursion(0, nums, new ArrayDeque<>(), 0);
        return ans;
    }

    public void recursion(int index, int nums[], Deque<Integer> path, int count) {
        if (index == nums.length) {
            if (path.size() > max) {
                max = count;
                ans = new ArrayList<>(path);
            }
            return;
        }
        path.addLast(nums[index]);
        for (int i = index + 1; i <= nums.length; i++) {
            if (i == nums.length) {
                recursion(i, nums, path, count);
            } else if (nums[i] % nums[index] == 0) {
                path.addLast(nums[i]);
                recursion(i, nums, path, count + 1);
                path.removeLast();
            }
        }
        path.removeLast();
    }







    /*
    f(index) 表示的 是 以 index 开头的 最大 整除子集的个数
    时间复杂度 O(2 ^ N)
    空间复杂度 O(1)
     */
    public int recursion(int index, int nums[]) {
        if (index == nums.length - 1) {
            return 1;
        }
        int ans = 1;
        for (int i = index + 1;i < nums.length;i++) {
            if (nums[i] % nums[index] == 0){
                ans =Math.max( ans,recursion(i,nums) + 1);
            }
        }
        return ans;
    }
    /*
    改成动态规划之后
    时间复杂度O(N ^ 2)
    空间 O(N), 因为只有一个可变参数 , 但是递归中存在循环枚举行为

    path[] 数组进行一个 路径 记录(也就是 从那条路过来的!)
    path[index] 表示的是 以index 开头的最长分割子集, 是从哪个 下标过来的
    path[index] = index 表示, 当前 没有从其他方向转移过来,也就是分割子集,只有 自己本身!
     */
    public List<Integer> solutionDp(int nums[]){
        int dp[] = new int[nums.length] , path[] = new int[nums.length];
        dp[nums.length - 1] = 1; // 初始化basecase dp
        path[nums.length - 1] = nums.length - 1; //  basecase path

        int ans = dp[nums.length - 1];

        // 排序 , 现在这个程度, 应该一眼 就能看出来吧!
        Arrays.sort(nums);

        for(int index = nums.length - 2;index >= 0;index--){
            dp[index] = 1;
            for(int i = index + 1;i < nums.length;i++){
                if(nums[i] % nums[index] == 0){
//                    dp[index] = Math.max(dp[i],dp[index]);
                    if(dp[index] < dp[i] + 1){
                        path[index] = i;
                        dp[index] = dp[i] + 1;
                    }
                }
            }
            ans = Math.max(ans,dp[index]);
        }

        List<Integer> res = new ArrayList<>();
        int i;
        for( i = 0;i < nums.length;i++){
            if(dp[i] == ans){
                break;
            }
        }
        for(int count = 0;count < ans ;i = path[i], count++){
            res.add(nums[i]);
        }

        return res;
    }

    @Test
    public void test() {
        int nums[] = {1,2,3};
//        int nums[] = {3, 4, 16, 8};
//        int nums[] = {1, 2, 4, 8};
//        List<Integer> solution = solution(nums);
//        System.out.println(solution);
        System.out.println(recursion(0,nums));
        System.out.println(solutionDp(nums));
    }

}
